class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board string字符串vector 
     * @param word string字符串 
     * @return bool布尔型
     */
     vector<int> dx={1,-1,0,0};
     vector<int> dy={0,0,1,-1};
     std::array<std::array<bool,110>,110> st={false};

    bool dfs(int i,int j,string& word,vector<string>& board,int k)
    {
       //应当先检查这一层是否匹配，并不是说到达这一层最后一个字母就一定匹配。注意两个出口的判断顺序
        if(word[k]!=board[i][j])
        {
            return false;
        }
        
         if(k==word.size()-1)
        {
            return true;
        }

        int ret=0;
        st[i][j]=true;
        for(int p=0;p<4;p++)
        {
            int x=i+dx[p];int y=j+dy[p];
            if(x<0||x>=board.size()||y<0||y>=board[0].size()||st[x][y]==true) continue;
            
            ret=dfs(x,y,word,board,k+1);
            
            if(ret==true)
            {
                st[i][j]=false;
                return true;
            }
        }
        st[i][j]=false;
        return false;
    }
    bool exist(vector<string>& board, string word) {
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[i].size();j++)
            {
                if(word[0]==board[i][j])
                {
                    //每次进去都得初始化为false;
                    for (auto& row : st) {
                        row.fill(false);  // 每一行填充 false
                    }
                    st[i][j]=true;
                    int ret=dfs(i,j,word,board,0);
                    if(ret) return true;
                }
            }
        }
        return false;
    }
};